package t_31

func nextPermutation(nums []int) {
	n := len(nums)
	if n < 2 {
		return
	}

	// 从后置位找到第一个逆序
	i := n - 2
	for i > 0 && nums[i] >= nums[i+1] {
		i--
	}

	//
	if i >= 0 {
		j := n - 1
		for j >= 0 && nums[i] >= nums[j] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}

	if i+1 < n {
		reverse(nums[i+1:])
	}

}

// 反转 数组切片
func reverse(a []int) {
	for i, n := 0, len(a); i < n/2; i++ {
		a[i], a[n-1-i] = a[n-1-i], a[i]
	}
}
